package com.wj.algorithm.lintcode;

import com.wj.algorithm.ArrayUtil;

public class P139 {

    public int[] subarraySumClosest(int[] nums) {
        if(nums == null) {
            return new int[0];
        }
        int len = nums.length;
        
        int[] temp = new int[len];
        
        int i = 0;
        temp[i] = nums[i];
        for(int j = i; j < len; j ++) {
            //包含j+j
            int prev = 0;
            //默认j=i的时候，v值保留自己，因为i和j下标相同，同一个数；为了兼容后续的累加和，这里只保留一个值
            int v = nums[j];
            if(j > i) {
                //如果有上一个，则记录累加和
                prev = temp[j - 1];
                v = nums[j] + prev;
            }
            temp[j] = v;
        }

        int left = 0;
        int right = 0;
        int distance = Integer.MAX_VALUE;
        System.out.println(ArrayUtil.toString(nums));
        System.out.println();
        for(i = 0; i < len; i ++) {
            System.out.println(i+"\t"+ArrayUtil.toString(temp) + "\t\t[" + left + ", " + right + "] \t distance:" + distance);
            for(int j = i + 1; j < len; j ++) {
                int v = temp[j];
                if(Math.abs(v - 0) < distance) {
                    distance = Math.abs(v - 0);
                    left = i;
                    right = j;
                }
                temp[j] = temp[j] - nums[i];
            }
        }
        
        int[] rs = new int[2];
        rs[0] = left;
        rs[1] = right;
        return rs;
    }
    
    public static void main(String[] args) {
        long b = System.currentTimeMillis();
        System.out.println(ArrayUtil.toString(new P139().subarraySumClosest(new int[]{6,-4,-8,3,1,7})));
//        System.out.println(ArrayUtil.toString(new P139().subarraySumClosest(ArrayUtil.readIn(15))));
        System.out.println(System.currentTimeMillis() - b);
    }
}
